import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution652 { 
    
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        Set<String> s1=new HashSet<>();
        Set<String> s2=new HashSet<>();
        List<TreeNode> ans=new ArrayList<>();
        dfs(root,s1,s2,ans);
        return ans;
    }

    private String dfs(TreeNode root,Set<String> s1,Set<String> s2,List<TreeNode> ans) {
        if (root==null){
            return "";
        }
        StringBuilder stringBuilder=new StringBuilder();
        stringBuilder.append(root.val).append('(');
        stringBuilder.append(dfs(root.left,s1,s2,ans));
        stringBuilder.append(")(");
        stringBuilder.append(dfs(root.right,s1,s2,ans));
        stringBuilder.append(')');
        String t=stringBuilder.toString();
        if (!s1.contains(t)){
            s1.add(t);
        }else{
            if (!s2.contains(t)){
                s2.add(t);
                ans.add(root);
            }
        }
        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        System.out.println(new Solution652().findDuplicateSubtrees(new TreeNode(0,
                new TreeNode(0,new TreeNode(0),null),
                new TreeNode(0,null,
                        new TreeNode(0,null, new TreeNode(0))))).size());
    }
}
